#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include "tp2.h"

  /*
   * Faz a troca de dois elementos da lista quando necessario.
   */
  void Troca(PK *lista,int a,int b){
    PK aux;
    aux=lista[a];
    lista[a]=lista[b];
    lista[b]=aux;
    return;
  }

  /*
   * Retorna TRUE se 'a' vier antes de 'b'. Se 'b' vier antes de 'a' retorna FALSE.
   */
  int VerificaOrdem(PK a, PK b){
    int i=0;
    for(i=0;i<200;i++){
      if(a.titulo[i]<b.titulo[i]){
        return TRUE;
      }
      if(a.titulo[i]>b.titulo[i]){
        return FALSE;
      }
    }
    return TRUE;
  }

  /*
   * Ordena a lista de chaves primarias utilizando
   * o quicksort.
   */
  void Ordena(PK *lista,int inicio,int fim){
    int i=inicio,j=fim,pivo=(inicio+fim)/2;
    if(fim==inicio){
      return;
    }
  /*
   * Coloca o pivo em seu lugar final, rearranjando
   * os elementos de forma que todos os que vierem
   * antes alfabeticamente, fiquem a sua "esquerda"
   * e os que vierem alfabeticamente depois, fiquem
   * a sua "direita".
   */
    while(i<j){
      if((pivo!=i)&&(pivo!=j)){
        if((VerificaOrdem(lista[i],lista[pivo])==TRUE)&&(VerificaOrdem(lista[pivo],lista[j])==TRUE)){
          i++;
          j--;
        }
        else if((VerificaOrdem(lista[pivo],lista[i])==TRUE)&&(VerificaOrdem(lista[pivo],lista[j])==TRUE)){
          j--;
        }
        else if((VerificaOrdem(lista[i],lista[pivo])==TRUE)&&(VerificaOrdem(lista[j],lista[pivo])==TRUE)){
          i++;
        }
        else if((VerificaOrdem(lista[pivo],lista[i])==TRUE)&&(VerificaOrdem(lista[j],lista[pivo])==TRUE)){
          Troca(lista,i,j);
          i++;
          j--;
        }
      }
      if(pivo==i){
        if(VerificaOrdem(lista[pivo],lista[j])==TRUE){
          j--;
        }
        else if(VerificaOrdem(lista[j],lista[pivo])==TRUE){
          Troca(lista,pivo,j);
          pivo=j;
          i++;
        }
      }
      if(pivo==j){
        if(VerificaOrdem(lista[i],lista[pivo])==TRUE){
          i++;
        }
        else if(VerificaOrdem(lista[pivo],lista[i])==TRUE){
          Troca(lista,i,pivo);
          pivo=i;
          j--;
        }
      }
    }
  /*
   * Se a etapa estiver pronta(o pivo ja
   * estiver em seu lugar final), faz-se
   * a chamada recursiva conveniente.
   */
    if((pivo!=fim)&&(pivo!=inicio)){
      Ordena(lista,inicio,pivo-1);
      Ordena(lista,pivo+1,fim);
      return;
    }
    if(pivo==fim){
      Ordena(lista,inicio,pivo-1);
      Ordena(lista,pivo,fim);
      return;
    }
    if(pivo==inicio){
      Ordena(lista,inicio,pivo);
      Ordena(lista,pivo+1,fim);
      return;
    }
  }
